home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / stopper / strlist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  14.9 KB  |  506 lines
  1.  
  2. /*******************************   strlist.c   *********************************
  3.  
  4.     Purpose: String list abstract data type implementation.
  5.  
  6.     Notes:   This module implements a straightforward string ordered list
  7.              abstract data type.  It is optimized for appending and deleting
  8.              from the end of the list.  Since they are ordered lists, string
  9.              lists may be sorted, and their members are addressed by ordinal
  10.              position (starting from 0).
  11. **/
  12.  
  13. #include <stdio.h>
  14. #include <memory.h>
  15. #include <malloc.h>
  16. #include <string.h>
  17.  
  18. #include "strlist.h"
  19.  
  20. /******************************************************************************/
  21. /******************   Private Defines and Data Structures   *******************/
  22.  
  23. #define FALSE                          0
  24. #define TRUE                           1
  25. #define EOS                          '\0'
  26.  
  27. #define INCREMENT                     32    /* increase size by this much */
  28. #define MAX_LINE                     128    /* when reading text files */
  29.  
  30. typedef struct _StrListStruct {
  31.  
  32.                short size;             /* current length of the list */
  33.                short max_size;         /* room for this many strings */
  34.                char **string;          /* the string array */
  35.  
  36.                } StrListStruct;
  37.  
  38.             /*********   GetMemory and FreeMemory Macros   ********/
  39.  
  40. #define GetMemory(b,s)                ( (b) ? realloc(b,s) : malloc(s) )
  41. #define FreeMemory(b)                 ( (void)free( b ) )
  42.  
  43. /******************************************************************************/
  44. /**********************   Private Routine Declarations   **********************/
  45.  
  46. #ifdef __STDC__
  47.  
  48. static int  ExpandArray( StrList list );
  49. static void ISort( char *string, int lb, int ub );
  50. static void QSort( char **string, int lb, int ub );
  51.  
  52. #else
  53.  
  54. static int  ExpandArray( /* list */ );
  55. static void ISort( /* string, lb, ub */ );
  56. static void QSort( /* string, lb, ub */ );
  57.  
  58. #endif
  59.  
  60. /*FN**************************************************************************
  61.  
  62.          ExpandArray( list )
  63.  
  64.    Returns: int -- TRUE (1) on success, FALSE (0) otherwise
  65.  
  66.    Purpose: Increase the string array to hold more data
  67.  
  68.    Plan:    Part 1: Increase the maximum list size to its new value
  69.             Part 2: Allocate a new chunk of memory
  70.             Part 3: Return an indication of success
  71.  
  72.    Notes:   None
  73. **/
  74.  
  75. static int
  76. ExpandArray( list )
  77.    StrList list;   /* in: string list whose string array is enlarged */
  78.    {
  79.  
  80.          /* Part 1: Increase the maximum list size to its new value */
  81.    list->max_size += INCREMENT;
  82.  
  83.                   /* Part 2: Allocate a new chunk of memory */
  84.    list->string = (char **)GetMemory( (char *)list->string,
  85.                                       (list->max_size*sizeof(char *)) );
  86.  
  87.                  /* Part 3: Return an indication of success */
  88.    return( (list->string) ? TRUE : FALSE );
  89.  
  90.    } /* ExpandArray */
  91.  
  92. /*FN**************************************************************************
  93.  
  94.          ISort( string, lb, ub )
  95.  
  96.    Returns: void
  97.  
  98.    Purpose: Insertion sort a string array forward using strcmp ordering
  99.  
  100.    Plan:    Part 1: Put smallest in place as a sentinal
  101.             Part 2: Insert as necessary
  102.  
  103.    Notes:   None
  104. **/
  105.  
  106. static void
  107. ISort( string, lb, ub )
  108.    char **string;   /* in/out: string array sorted */
  109.    int lb,ub;       /* in: array bounds for sort */
  110.    {
  111.    register int i,j;  /* for scanning through the list */
  112.    char *tmp;         /* for swaps */
  113.  
  114.                /* Part 1: Put smallest in place as a sentinal */
  115.    for ( j = lb, i = lb+1; i <= ub; i++ )
  116.       if ( 0 < strcmp(string[j],string[i]) ) j = i;
  117.    tmp = string[lb]; string[lb] = string[j]; string[j] = tmp;
  118.  
  119.                        /* Part 2: Insert as necessary */
  120.    for ( i = lb+2; i <= ub; i++ )
  121.       {
  122.       tmp = string[i];
  123.       for ( j = i; 0 < strcmp(string[j-1],tmp); j-- ) string[j] = string[j-1];
  124.       string[j] = tmp;
  125.       }
  126.  
  127.    } /* ISort*/
  128.  
  129. /*FN**************************************************************************
  130.  
  131.          QSort( string, lb, ub )
  132.  
  133.    Returns: void
  134.  
  135.    Purpose: Quicksort an array of strings forward using strcmp ordering
  136.  
  137.    Plan:    Part 1: Use insertion sort of the list is short
  138.             Part 2: Do median of three pivot value selection
  139.             Part 3: Put the pivot out of the way at the top
  140.             Part 5: Swap the pivot back into the mid of the list
  141.             Part 6: Recursively sort the sublists
  142.  
  143.    Notes:   Standard quicksort function with the two main enhancements:
  144.             median of three partitioning to find a good pivot value,
  145.             and sorting small arrays with insertion sort.
  146. **/
  147.  
  148. static void
  149. QSort( string, lb, ub )
  150.    char **string;  /* in/out: string array sorted */
  151.    int lb,ub;      /* in: array bounds for sort */
  152.    {
  153.    register int lft;  /* list pointer that closes from the left */
  154.    register int rgt;  /* list pointer that closes from the right */
  155.    register int mid;  /* index of the median of three value */
  156.    char *tmp;         /* for string pointer swaps */
  157.    char *pivot;       /* the pivot value string */
  158.  
  159.               /* Part 1: Use insertion sort of the list is short */
  160.    if ( ub-lb < 12 ) { ISort( string, lb, ub ); return; }
  161.  
  162.              /* Part 2: Do median of three pivot value selection */
  163.    mid = (lb+ub)/2;
  164.    if ( strcmp(string[mid],string[lb]) < 0 )
  165.       { tmp = string[mid]; string[mid] = string[lb]; string[lb] = tmp; }
  166.    if ( strcmp(string[ub],string[mid]) < 0 )
  167.       { tmp = string[mid]; string[mid] = string[ub]; string[ub] = tmp; }
  168.    if ( strcmp(string[mid],string[lb]) < 0 )
  169.       { tmp = string[mid]; string[mid] = string[lb]; string[lb] = tmp; }
  170.  
  171.              /* Part 3: Put the pivot out of the way at the top */
  172.    tmp = string[mid]; string[mid] = string[ub-1]; string[ub-1] = tmp;
  173.  
  174.                  /* Part 4: Partition around the pivot value */
  175.    lft = lb;
  176.    rgt = ub-1;
  177.    pivot = string[ub-1];
  178.    do
  179.       {
  180.       do lft++; while ( strcmp(string[lft],pivot) < 0 );
  181.       do rgt--; while ( strcmp(pivot,string[rgt]) < 0 );
  182.       tmp = string[lft]; string[lft] = string[rgt]; string[rgt] = tmp;
  183.       }
  184.    while ( lft < rgt );
  185.  
  186.          /* Part 5: Swap the pivot back into the mid of the list */
  187.    string[rgt] = string[lft]; string[lft] = string[ub-1]; string[ub-1] = tmp;
  188.  
  189.                   /* Part 6: Recursively sort the sublists */
  190.    QSort( string, lb, lft-1 );
  191.    QSort( string, rgt+1, ub );
  192.  
  193.    } /* QSort */
  194.  
  195. /******************************************************************************/
  196. /**********************   Public Routine Declarations   ***********************/
  197.  
  198. /*FN***************************************************************************
  199.  
  200.          StrListAppend( list, string )
  201.  
  202.    Returns: void
  203.  
  204.    Purpose: Place a string on the end of a string list
  205.  
  206.    Plan:    Part 1: Standard parameter sanity check
  207.             Part 2: Expand the list as necessary
  208.             Part 3: Append the new string to the tail
  209.  
  210.    Notes:   None
  211. **/
  212.  
  213. void
  214. StrListAppend( list, string )
  215.    StrList list;   /* in/out: list appended to */
  216.    char *string;   /* in: the appended string */
  217.    {
  218.    int length;  /* of the added string and its terminator */
  219.  
  220.                  /* Part 1: Standard parameter sanity check */
  221.    if ( !list || !string ) return;
  222.  
  223.                    /* Part 2: Expand the list as necessary */
  224.    if ( (list->size == list->max_size) && !ExpandArray(list) ) return;
  225.  
  226.                  /* Part 3: Append the new string to the tail */
  227.    length = strlen( string ) + 1;
  228.    list->string[list->size] = GetMemory( NULL, length );
  229.    (void)memcpy( list->string[list->size], string, length );
  230.    list->size++;
  231.  
  232.    } /* StrListAppend */
  233.  
  234. /*FN***************************************************************************
  235.  
  236.          StrListAppendFile( list, filename )
  237.  
  238.    Returns: void
  239.  
  240.    Purpose: Place all lines from a file on the end of a string list
  241.  
  242.    Plan:    Part 1: Standard parameter sanity check
  243.             Part 2: Expand the list as necessary
  244.             Part 3: Append the new string to the tail
  245.  
  246.    Notes:   None
  247. **/
  248.  
  249. void
  250. StrListAppendFile( list, filename )
  251.    StrList list;     /* in/out: list appended to */
  252.    char *filename;   /* in: the appended file */
  253.    {
  254.    FILE *file;            /* file handle for the text input file */
  255.    char buffer[MAX_LINE]; /* for storing text input file lines */
  256.    int length;            /* of the added string and its terminator */
  257.    register int i;        /* for looping through the TextBlock lines */
  258.  
  259.                  /* Part 1: Standard parameter sanity check */
  260.    if ( !list || !filename ) return;
  261.  
  262.              /* Part 2: Open the text input file; check for error */
  263.    if ( NULL == (file = fopen(filename,"r")) ) return;
  264.  
  265.               /* Part 3: Append to the list, checking for errors */
  266.    while ( NULL != fgets(buffer,MAX_LINE,file) )
  267.       {
  268.       if ( (list->size == list->max_size) && !ExpandArray(list) ) return;
  269.  
  270.       i = list->size;
  271.       length = strlen( buffer );
  272.       list->string[i] = GetMemory( NULL, (unsigned)length );
  273.       if ( NULL == list->string[i] ) return;
  274.       (void)memcpy( list->string[i], buffer, length );
  275.       list->string[i][length-1] = EOS;
  276.       list->size++;
  277.       }
  278.  
  279.                     /* Part 4: Close the text input file */
  280.    (void)fclose( file );
  281.  
  282.    } /* StrListAppendFile */
  283.  
  284. /*FN***************************************************************************
  285.  
  286.          StrListCreate()
  287.  
  288.    Returns: StrList -- a new structure, or NULL on failure
  289.  
  290.    Purpose: Allocate and initialize a new string list structure
  291.  
  292.    Plan:    Part 1: Allocate space for the string list object
  293.             Part 2: Initialize the structure fields
  294.             Part 3: Return the new string list
  295.  
  296.    Notes:   None
  297. **/
  298.  
  299. StrList
  300. StrListCreate()
  301.    {
  302.    StrList list;  /* the new list returned */
  303.  
  304.             /* Part 1: Allocate space for the string list object */
  305.    if ( !(list = (StrList)GetMemory(NULL,sizeof(StrListStruct))) )
  306.       return( NULL );
  307.  
  308.                  /* Part 2: Initialize the structure fields */
  309.    list->string = NULL;
  310.    list->size = list->max_size = 0;
  311.    if ( !ExpandArray(list) )
  312.       { FreeMemory( (char *)list ); return( NULL ); }
  313.  
  314.                     /* Part 3: Return the new string list */
  315.    return( list );
  316.  
  317.    } /* StrListCreate */
  318.  
  319. /*FN***************************************************************************
  320.  
  321.          StrListDestroy( list )
  322.  
  323.    Returns: void
  324.  
  325.    Purpose: Deallocate the space used for a string list
  326.  
  327.    Plan:    Part 1: Standard parameter sanity check
  328.             Part 2: Free all the space
  329.  
  330.    Notes:   None
  331. **/
  332.  
  333. void
  334. StrListDestroy( list )
  335.    StrList list;    /* in: the list destroyed */
  336.    {
  337.    register int i;  /* for scanning through the list */
  338.  
  339.                  /* Part 1: Standard parameter sanity check */
  340.    if ( !list ) return;
  341.  
  342.                         /* Part 2: Free all the space */
  343.    for ( i = 0; i < list->size; i++ ) FreeMemory( (char *)(list->string[i]) );
  344.    FreeMemory( (char *)list );
  345.  
  346.    } /* StrListDestroy */
  347.  
  348. /*FN***************************************************************************
  349.  
  350.          StrListEqual( list1, list2 )
  351.  
  352.    Returns: int -- TRUE if the lists are equivalent, FALSE otherwise
  353.  
  354.    Purpose: See if two lists have identical elements
  355.  
  356.    Plan:    Part 1: Say not equal if the parameters are bad
  357.             Part 2: Say not equal if sizes are different
  358.             Part 3: Compare lists element by element
  359.             Part 4: Say equal if everything checks out
  360.  
  361.    Notes:   None
  362. **/
  363.  
  364. int
  365. StrListEqual( list1, list2 )
  366.    StrList list1,list2;   /* in: lists compared */
  367.    {
  368.    register int i;  /* for scanning through the lists */
  369.  
  370.              /* Part 1: Say not equal if the parameters are bad */
  371.    if ( !list1 || !list2 ) return( FALSE );
  372.  
  373.                /* Part 2: Say not equal if sizes are different */
  374.    if ( list1->size != list2->size ) return( FALSE );
  375.  
  376.               /* Part 3: Compare the lists element by element */
  377.    for ( i = 0; i < list1->size; i++ )
  378.       if ( *(list1->string[i]) != *(list2->string[i]) )
  379.          return( FALSE );
  380.       else if ( 0 != strcmp(list1->string[i],list2->string[i]) )
  381.          return( FALSE );
  382.  
  383.                /* Part 5: Say equal if everything checks out */
  384.    return( TRUE );
  385.  
  386.    } /* StrListEqual */
  387.  
  388. /*FN***************************************************************************
  389.  
  390.          StrListPeek( list, index )
  391.  
  392.    Returns: char * -- pointer to the requested string; NULL on error
  393.  
  394.    Purpose: Peek a string by its list index
  395.  
  396.    Plan:    Part 1: Standard parameter sanity check
  397.             Part 2: Return the requested string
  398.  
  399.    Notes:   Note that this function is a hole in the data type encapsulation:
  400.             it should return a copy, but this would force the consumer to
  401.             deallocate the string.  Design call.
  402. **/
  403.  
  404. char *
  405. StrListPeek( list, index )
  406.    StrList list;   /* in: list retrieved from */
  407.    int index;      /* in: which string to fetch */
  408.    {
  409.                  /* Part 1: Standard parameter sanity check */
  410.    if ( !list || (index < 0) || (list->size <= index) ) return( NULL );
  411.  
  412.                    /* Part 2: Return the requested string */
  413.    return( list->string[index] );
  414.  
  415.    } /* StrListPeek */
  416.  
  417. /*FN***************************************************************************
  418.  
  419.          StrListSize( list )
  420.  
  421.    Returns: int -- the size of the list, 0 on error
  422.  
  423.    Purpose: Grab the list size
  424.  
  425.    Plan:    Return the list size field
  426.  
  427.    Notes:   None
  428. **/
  429.  
  430. int
  431. StrListSize( list )
  432.    StrList list;   /* in: list queried */
  433.    {
  434.  
  435.    if ( !list ) return( 0 ); else return( list->size );
  436.  
  437.    } /* StrListSize */
  438.  
  439. /*FN***************************************************************************
  440.  
  441.          StrListSort( list )
  442.  
  443.    Returns: void
  444.  
  445.    Purpose: Sort a single string list using strcmp ordering
  446.  
  447.    Plan:    Part 1: Do parameter sanity checks, then sort
  448.  
  449.    Notes:   None
  450. **/
  451.  
  452. void
  453. StrListSort( list )
  454.    StrList list;   /* in/out: list sorted */
  455.    {
  456.              /* Part 1: Do parameter sanity checks, then sort */
  457.    if ( !list ) return;
  458.    QSort( list->string, 0, list->size-1 );
  459.  
  460.    } /* StrListSort */
  461.  
  462. /*FN***************************************************************************
  463.  
  464.          StrListUnique( list )
  465.  
  466.    Returns: void
  467.  
  468.    Purpose: Sort a single string list using strcmp ordering, then remove
  469.             duplicates.
  470.  
  471.    Plan:    Part 1: Do parameters sanity checks
  472.             Part 2: Sort the list
  473.             Part 3: Remove duplicate strings
  474.  
  475.    Notes:   None
  476. **/
  477.  
  478. void
  479. StrListUnique( list )
  480.    StrList list;   /* in/out: list sorted and uniqued */
  481.    {
  482.    register i,j;   /* counters for copying down over duplicates */
  483.  
  484.                     /* Part 1: Do parameter sanity checks */
  485.    if ( !list ) return;
  486.  
  487.                        /* Part 2: Sort the list */
  488.    QSort( list->string, 0, list->size-1 );
  489.  
  490.                    /* Part 3: Remove duplicate strings */
  491.    if ( 1 < list->size )
  492.       {
  493.       for ( j = 0, i = 1; i < list->size; i++ )
  494.          {
  495.          if ( 0 == strcmp(list->string[i],list->string[j]) )
  496.             (void)free( list->string[j] );
  497.          else
  498.             j++;
  499.          if ( j < i ) list->string[j] = list->string[i];
  500.          }
  501.       list->size = j + 1;
  502.       }
  503.  
  504.    } /* StrListUnique */
  505.  
  506.